package com.sicheng.lc.周赛.分类.图论.枚举or排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/23 20:06
 */
public class 节点序列的最大得分 {
    //https://leetcode.cn/problems/maximum-score-of-a-node-sequence/
    public int maximumScore(int[] scores, int[][] edges) {

        int n = scores.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            g[x].add(new int[]{scores[y], y});
            g[y].add(new int[]{scores[x], x});
        }


        int ans = 0;
        for (int i = 0; i < g.length; i++) {
            if (g[i].size() > 3) {
                g[i].sort((a, b) -> b[0] - a[0]);
                g[i] = g[i].subList(0, 3);
            }
        }

        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            for (int[] tx : g[x]) {
                int a = tx[1];
                for (int[] ty : g[y]) {
                    int b = ty[1];
                    if (a != b && x != a && b != y) {
                        ans = Math.max(ans, scores[x] + scores[y] + scores[a] + scores[b]);
                    }
                }
            }
        }

        return ans;
    }
}
